package com.yiwenup.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/chou-shu-lcof/
 **/
public class No049 {
    /**
     * 执行用时：2 ms, 在所有 Java 提交中击败了99.27%的用户
     * 内存消耗：37.1 MB, 在所有 Java 提交中击败了96.97%的用户
     */
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;

        int a = 0, b = 0, c = 0;
        for (int i = 1; i < n; i++) {
            int xa = 2 * dp[a];
            int xb = 3 * dp[b];
            int xc = 5 * dp[c];
            dp[i] = Math.min(Math.min(xa, xb), xc);

            if (dp[i] == xa) a++;
            if (dp[i] == xb) b++;
            if (dp[i] == xc) c++;
        }

        return dp[n - 1];
    }
}